{
 "metadata": {
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.8.3-final"
  },
  "orig_nbformat": 2,
  "kernelspec": {
   "name": "python_defaultSpec_1597726204628",
   "display_name": "Python 3.8.3 64-bit"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2,
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "给定一个单链表，其中的元素按升序排序，将其转换为高度平衡的二叉搜索树。\n",
    "\n",
    "本题中，一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。\n",
    "\n",
    "示例:\n",
    "```\n",
    "给定的有序链表： [-10, -3, 0, 5, 9],\n",
    "\n",
    "一个可能的答案是：[0, -3, 9, -10, null, 5], 它可以表示下面这个高度平衡二叉搜索树：\n",
    "\n",
    "      0\n",
    "     / \\\n",
    "   -3   9\n",
    "   /   /\n",
    " -10  5\n",
    "```\n",
    "来源：力扣（LeetCode）\n",
    "链接：https://leetcode-cn.com/problems/convert-sorted-list-to-binary-search-tree\n",
    "著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "思路\n",
    "\n",
    "除了一开始的找到中位数可以想到，后面的如何构造高度平衡的二叉搜索树，是想不到的，想想自己以前也没写过。\n",
    "\n",
    "步骤：\n",
    "\n",
    "1. 找到链表的中间节点\n",
    "2. 左边的构造左树，右边的构造右数"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "from leetcode_test import TreeNode, ListNode"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Solution:\n",
    "    def sortedListToBST(self, head: ListNode) -> TreeNode:\n",
    "        l = []\n",
    "        while head:\n",
    "            l.append(head.val)\n",
    "            head = head.next\n",
    "        \n",
    "        length = len(l)\n",
    "        left = 0\n",
    "        def build_tree(left, right) -> ListNode:\n",
    "            if left == right:\n",
    "                return # 当left == 0, right == 1时，mid会等于0， 这样这个tree的左节点就是 root.left = build_tree(0, 0), 就会返回None\n",
    "            print(left, right)\n",
    "            mid = (left + right) // 2\n",
    "            root = TreeNode(l[mid])\n",
    "            print(\"root=\", root)\n",
    "            root.left = build_tree(left, mid) # 让左节点在（0,1)，落在0\n",
    "\n",
    "            root.right = build_tree(mid+1, right) # 让右节点(1,1) 返回None\n",
    "            return root\n",
    "        \n",
    "        return build_tree(left, length)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {
    "tags": []
   },
   "outputs": [
    {
     "output_type": "stream",
     "name": "stdout",
     "text": "0 5\nroot= <TreeNode: 0>\n0 2\nroot= <TreeNode: -3>\n0 1\nroot= <TreeNode: -10>\n3 5\nroot= <TreeNode: 9>\n3 4\nroot= <TreeNode: 5>\n[0, -3, 9, -10, None, 5, None]\n"
    }
   ],
   "source": [
    "list_node = ListNode.create([-10, -3, 0, 5, 9])\n",
    "tree = Solution().sortedListToBST(list_node)\n",
    "print(tree.get_value())"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 总结"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```python\n",
    "root.left = build_tree(left, mid) # 让左节点在（0,1)，落在0\n",
    "\n",
    "root.right = build_tree(mid+1, right) # 让右节点(1,1) 返回None\n",
    "```\n",
    "\n",
    "看了半天，也就这两句比较有灵性，这样的算法构建出来的，二叉树也绝对是平衡的，递归真的太适合二叉树了。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 复习"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "2020-8-21 复习了一下，结果忘记写\n",
    "\n",
    "```\n",
    "if left == right:\n",
    "    return\n",
    "```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ]
}